package com.ry.day1129;

public class LC118 {

    static class Solution {
        /**
         * @param s: A string
         * @param t: A string
         * @return: Count the number of distinct subsequences
         */
        public int numDistinct(String s, String t) {
            //动态规划，样本对应模型，考虑以某字符结尾的情况
            if(s ==null || t==null || s.length() < t.length()) return 0;
            if(!s.equals("") && t.equals("")) return 1;
            return f(s.toCharArray(),t.toCharArray());
        }
        public int f(char[] s,char[] t){
            int n = s.length;
            int m= t.length;
            int[][] cache = new int[n][m];
            for (int i = 0; i <n ; i++) {
                for (int j = 0; j <m ; j++) {
                    cache[i][j] = -1;
                }
            }
            int ans = dfs(s,t,n-1,m-1,cache);
            return ans <0 ?0: ans;
        }

        public int dfs(char[] s,char[] t,int i,int j,int[][] cache){
            if(cache[i][j] !=-1) return cache[i][j];
            int ans =-1;
            if(i==0 && j==0){
                ans= s[i]==t[j] ?1 :0;
            }else if(j==0){
                if(s[i] ==t[j])
                    ans = dfs(s,t,i-1,j,cache)+1;
                else
                    ans = dfs(s,t,i-1,j,cache);
            }else if(i==0){
               ans=0;
            }else{
                //普遍位置怎么求
                ans = dfs(s,t,i-1,j,cache);
                if(s[i]==t[j]){
                    ans+= dfs(s,t,i-1,j-1,cache);
                }
            }
            cache[i][j] =ans;
            return ans;
        }
    }


    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.numDistinct("rabbbit","rabbit"));
        System.out.println(obj.numDistinct("abcd",""));
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
118 · 不同的子序列
算法
中等
通过率
38%

题目
题解18
笔记
讨论99+
排名
记录
描述
给定字符串 S 和 T, 字符串S中有多少个子序列字符串和字符串T相同。

子序列字符串是原始字符串删除一些(或零个)字符之后得到的字符串, 并且不能改变剩下字符的相对位置。(比如 "ACE" 是 ABCDE 的一个子序列, 而 "AEC" 不是)

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


l
e
n
(
S
)
<
=
200
len(S)<=200
l
e
n
(
T
)
<
=
30
len(T)<=30

样例
样例 1：

输入：

S = "rabbbit"
T = "rabbit"
输出：

3
解释：

你可以删除 S 中的任意一个 'b', 所以一共有 3 种方式得到 T.

样例 2：

输入：

S = "abcd"
T = ""
输出：

1
解释：

只有删除 S 中的所有字符这一种方式得到 T

挑战
挑战时间复杂度 O(
n
2
n
2
 ), 空间复杂度 O(n) 的算法.

如果你不知道如何优化空间, O(
n
2
n
2
 ) 的空间复杂度也是可以通过的.

相关知识
学习《算法进阶：动态规划专题》课程中的6.16第六章作业—不同的子序列相关内容 ，了解更多相关知识！
标签
相关题目

29
交叉字符串
困难
推荐课程

*/
